home *** CD-ROM | disk | FTP | other *** search
/ EnigmA Amiga Run 1997 April / EnigmA AMIGA RUN 17 (1997)(G.R. Edizioni)(IT)[!][issue 1997-04][EAR-CD].iso / EARCD / comm / bbs / RPGBBSD3.lha / Documentation / Btree next >
Text File  |  1995-04-02  |  6KB  |  196 lines
  1. February 20, 1994
  2.  
  3.  
  4. These B tree functions were written allow rapid indexing to random files.
  5. They were the crucial element in creating the C program, Amiga Checkbook,
  6. published by Amiga World magazine.  B trees are balanced, multiway trees in
  7. which 4 keys are stored per node.  Examine the btree.h include file for the
  8. header and node layouts.  An example of a B tree layout when inserting keys
  9. a - z sequentially into an empty tree will look as follows:
  10.  
  11.                                    { i r }
  12.  
  13.         { c f }                    { l o }                    { u x }
  14.  
  15. { a b } { d e } { g h }    { j k } { m n } { p q }    { s t } { v w } { y z }
  16.  
  17.  
  18. This yields with a 50% packing efficiency with plenty of room for insertion
  19. of new keys.  As you can see, the tree is optimally balanced.
  20.  
  21. In using the B tree functions, it is important to understand how to save
  22. the keys and later retrieve them.  Keys are fixed-length character arrays
  23. defined at tree creation Bcreate().  Keys are case independent when sorted
  24. and searched from within the tree using strnicmp().  Keys can therefore be
  25. NULL-terminated or not, depending upon your needs.  For example, I store
  26. file cursor pointers with the keys, so they index an external, random file.
  27. To illustrate, I setup a date.tree file indexing appointments.master file
  28. like this:
  29.  
  30. #include <exec/types.h>
  31. #include <intuition/intuition.h>
  32. #include <btree.h>
  33. #include <stdio.h>
  34.  
  35. struct IntuitionBase *IntuitionBase;
  36.  
  37. struct B date;            /* B function structure */
  38.  
  39. struct date_rec {
  40.     UBYTE date[9];        /* YYYYMMDD and NULL format */
  41.     ULONG record;        /* File cursor pointer to master */
  42. } date_rec;
  43.  
  44. struct master_rec {
  45.     UBYTE name[31];        /* Person to meet */
  46.     UBYTE date[9];        /* Date */
  47.     UBYTE comment[41];        /* Free text */
  48. } appointment;
  49.  
  50. main()
  51. {
  52.     IntuitionBase=(struct IntuitionBase *)OpenLibrary("intuition.library",0L);
  53.  
  54.     Bcreate(&date,"date.tree",sizeof(struct date_rec));
  55.     if(date.Bstatus) {
  56.         printf("Could not Bcreate()!\n");
  57.         exit(TRUE);
  58.     }
  59.  
  60.     Bopen(&date,"date.tree");
  61.     if(date.Bstatus) {
  62.         printf("Could not Bopen()!\n");
  63.         exit(TRUE);
  64.     }
  65.  
  66.     strcpy(date_rec.date,"19900807");
  67.     date_rec.record=0;
  68.     Bstore(&date,&date_rec);
  69.     if(date.Bstatus)
  70.         printf("Could not Bstore()!\n");
  71.  
  72.     Bget(&date,&date_rec);
  73.     if(date.Bstatus)
  74.         printf("Could not Bget()!\n");
  75.  
  76.     date_rec.record=1;
  77.     Bupdate(&date,&date_rec);
  78.     if(date.Bstatus)
  79.         printf("Could not Bupdate()!\n");
  80.  
  81.     Bdelete(&date,&date_rec);
  82.     if(date.Bstatus)
  83.         printf("Could not Bdelete()!\n");
  84.  
  85.     Bclose(&date);
  86.     if(date.Bstatus) {
  87.         printf("Could not Bclose()!\n");
  88.         exit(TRUE);
  89.     }
  90.  
  91.     CloseLibrary(IntuitionBase);
  92. }
  93.  
  94.  
  95. This simply adds, gets, updates, deletes the key "19900807" from the B tree
  96. file date.tree.  Please note that you MUST Bget() the key BEFORE Bupdate()
  97. or Bdelete can be used.  This allows duplicate keys in the tree and YOU
  98. control which key is to be updated/deleted.
  99.  
  100. ------------------
  101. Send inquiries to:
  102. ------------------
  103.     Robert Hurst
  104.     11 Patricia Court
  105.     Warwick, RI  02889
  106.     BBS: (401) 738-1437
  107.  
  108.  
  109. For a good example on how to use these functions, examine the Banalyze.c
  110. and EditTree.c source files.
  111.  
  112. Here is the list of functions in the btree.library:
  113.  
  114. /***********************\
  115.  *  Create new B-Tree  *
  116. \***********************/
  117. void Bcreate(b,filename,kl)
  118. struct B *b;                /* Pointer to B structure */
  119. char *filename;                /* AmigaDOS filename */
  120. UWORD kl;                /* Maximum key length 1-65536 */
  121.  
  122. /****************************\
  123.  *  Open B-Tree for access  *
  124. \****************************/
  125. void Bopen(b,filename)
  126. struct B *b;                /* Pointer to B structure */
  127. char *filename;                /* AmigaDOS filename */
  128.  
  129. /******************\
  130.  *  Close B-Tree  *
  131. \******************/
  132. void Bclose(b)
  133. struct B *b;                /* Pointer to B structure */
  134.  
  135. /*************************************\
  136.  *  Search B-Tree for specified key  *
  137. \*************************************/
  138. void Bget(b,key)
  139. struct B *b;                /* Pointer to B structure */
  140. char *key;                /* Key to retrieve */
  141.  
  142. /******************************************\
  143.  *  Get next key in sequence from B-Tree  *
  144. \******************************************/
  145. void Bnext(b,key)
  146. struct B *b;                /* Pointer to B structure */
  147. char *key;                /* Next key in ascending sequence */
  148.  
  149. /**********************************************\
  150.  *  Get previous key in sequence from B-Tree  *
  151. \**********************************************/
  152. void Bprev(b,key)
  153. struct B *b;                /* Pointer to B structure */
  154. char *key;                /* Next key in descending sequence */
  155.  
  156.  
  157. /*************************\
  158.  *  Add a key to B-Tree  *
  159. \*************************/
  160. void Bstore(b,key)
  161. struct B *b;                /* Pointer to B structure */
  162. char *key;                /* Key to add */
  163.  
  164. /******************************\
  165.  *  Delete a key from B-Tree  *
  166. \******************************/
  167. void Bdelete(b,key)
  168. struct B *b;                /* Pointer to B structure */
  169. char *key;                /* Key to be deleted */
  170.  
  171. /*****************************\
  172.  *  Update record in B-Tree  *
  173. \*****************************/
  174. void Bupdate(b,key)
  175. struct B *b;                /* Pointer to B structure */
  176. char *key;                /* Update data in key */
  177.  
  178. /**********************************\
  179.  *  Support functions for B-Tree  *
  180. \**********************************/
  181. void Bputheader(b)
  182. struct B *b;                /* Pointer to B structure */
  183.  
  184. void Bgetnode(b,fp,bp)
  185. struct B *b;                /* Pointer to B structure */
  186. ULONG fp;                /* File cursor position */
  187. UBYTE bp;                /* Load which memory node (0-2) */
  188.  
  189. void Bputnode(b,fp,bp)
  190. struct B *b;                /* Pointer to B structure */
  191. ULONG fp;                /* File cursor position */
  192. UBYTE bp;                /* Save which memory node (0-2) */
  193.  
  194. ULONG Bfree(b)
  195. struct B *b;                /* Pointer to B structure */
  196.